package realQuestion.saibo;

import java.util.ArrayList;

public class Main1 {


//    class Main{
//        public static int  getMin(int j,int k){
//            int minCount=Integer.MAX_VALUE;
//            for (int i = 1; i <=13; i++) {
//                for (int l = 1; l <=13; l++) {
//                    int area=i*l;
//                    if (area==j*k){
//                        minCount=Math.min(minCount,Math.min(i,l));
//                    }
//
//                }
//            }
//            return  minCount;
//        }
//
//    }

    public String[] findMaxCommon (String stringA, String stringB) {
        // write code here
//        int[][] dp = lcsTable(stringA, stringB);
//        String[] lcs = getLCS(dp, stringA, stringB);
//
//        StringBuilder stringBuilder = new StringBuilder();
//        for (int i = 0; i <lcs.length; i++) {
//            stringBuilder.append(lcs[i]);
//        }
//        System.out.println(stringBuilder.toString());

        ArrayList<String> common= new ArrayList<>();
        for (int i = 0; i <stringA.length() ; i++) {
            String substring = stringA.substring(i);
            if (stringB.contains(substring)){
                common.add(substring);
            }
        }
        return  common.toArray(new String[common.size()]);


    }

    public int[][] lcsTable(String str1,String str2){
        int  m= str1.length();
        int n= str2.length();
        int[][] dp=new int[m+1][n+1];

        for (int i = 0; i <=m; i++) {
            for (int j = 0; j <=n; j++) {
                if (i==0||j==0){
                    dp[i][j]=0;
                }else  if (str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }

            }
        }
        return  dp;

    }

    public  String[]  getLCS(int[][] dp,String str1,String str2){
        int m= dp.length-1;
        int n=dp[0].length-1;
        int lcsLength=dp[m][n];
        String[] lcs=new String[lcsLength];
        int index=lcsLength-1;

        while (m>0&&n>0){
            if (str1.charAt(m-1)==str2.charAt(n-1)){
                lcs[index]=String.valueOf(str1.charAt(m-1));
                index--;
                m--;
                n--;
            }else  if (dp[m-1][n]>dp[m][n-1]){
                m--;
            }else {
                n--;
            }
        }
          String[] now=new String[lcs.length+4];
          now[0]="[";
          now[1]="\"";
          int temp=0;

        for (int i = 2; i < now.length ; i++) {
            if (i== now.length-2){
                now[i]="\"";
            }else  if (i== now.length-1){
                now[i]="]";
            }else {
                now[i]=lcs[temp++];
            }

        }
        return  now;
    }

    public static void main(String[] args) {
        Main1 main1 = new Main1();
        String[] maxCommon = main1.findMaxCommon("A new social, create your hip play show", "A new social, and create your hip show");
//        StringBuilder stringBuilder = new StringBuilder();
//        for (int i = 0; i < maxCommon.length; i++) {
//            if (i==0){
//                stringBuilder.append("[");
//                stringBuilder.append("\"");
//
//            }
//            stringBuilder.append(maxCommon[i]);
//
//        }
//        stringBuilder.append("\"");
//        stringBuilder.append("]");
//        System.out.println(stringBuilder.toString());
//        System.out.println(maxCommon);
    }
}
